package codeRandomThoughts.Test1005K次取反后最大化的数组和;

import java.util.Arrays;

public class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int index = 0;
        for (index = 0; index < nums.length; index++) {
            if (nums[index] >= 0) {
                //记录第一个大于0元素的位置
                break;
            }
        }

        //防止没有大于0的元素而越界
        if (index == nums.length) index = nums.length - 1;

        if (index > k - 1) {
            //把index之前k个元素取反
            for (int i = 0; i < k; i++) {
                nums[i] = -nums[i];
            }
        } else {
            int minIndex = index;
            for (int i = 0; i < index; i++) {
                nums[i] = -nums[i];
                if (nums[i] < nums[index]) {
                    minIndex = i;
                }
            }
            //还剩下(k - 1 - index)次机会,此时数组中都是正数,对最小的元素进行操作
            //判断奇偶,取反偶数次还是自己
            if ((k - index) % 2 != 0) {
                nums[minIndex] = -nums[minIndex];
            }
        }

        return Arrays.stream(nums).sum();
    }
}
